package sortTests;

import java.util.ArrayList;
import java.util.List;

public class MergeSort implements ISorter {

	@Override
	public void sort(List<Integer> array) {
		if (array.size() <= 1) return;
		sort(array.subList(0, array.size()/2));
		sort(array.subList(array.size()/2, array.size()));
		ArrayList<Integer> buffer = new ArrayList<Integer>();
		int i = 0;
		int j = array.size()/2;
		while ((i < array.size()/2)&&(j < array.size())) {
			if (array.get(i) < array.get(j)) {
				buffer.add(array.get(i));
				i++;
			} else {
				buffer.add(array.get(j));
				j++;
			}
		}
		if (i < array.size()/2) {
			buffer.addAll(array.subList(i, array.size()/2));
		}
		if (j < array.size()) {
			buffer.addAll(array.subList(j, array.size()));
		}
		for (int k = 0; k < array.size(); k++) {
			array.set(k, buffer.get(k));
		}
	}

}
